package com.kaizen.leet155;

import java.util.Arrays;

/**
 * 155.设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * push(x) —— 将元素 x 推入栈中。
 * pop() —— 删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/min-stack
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author kaizen
 * @date 2020/4/21 22:58
 */
public class MinStackKaizen {

    private int min = 0;

    private int[] data;

    private int size;

    private int capacity;

    private static final int DEFAULT_CAPACITY =  10;


    /** initialize your data structure here. */
    public MinStackKaizen() {
        data = new int[DEFAULT_CAPACITY];
        this.capacity = DEFAULT_CAPACITY;
        this.size = 0;

    }

    public void push(int x) {
        // 延迟初始化
        if (this.size == 0) {
            this.min = x;
        }else {
            this.min = Math.min(this.min, x);
        }
        if (this.size >= this.capacity) {
            grow();
        }
        data[this.size++] = x;
    }

    public void pop() {
        if (this.size <=0) {
            throw new IndexOutOfBoundsException("stack is empty");
        }
        int top = top();
        this.size --;
        if (size == 0) {
            this.capacity = DEFAULT_CAPACITY;
            this.min = 0;
            this.data = new int[DEFAULT_CAPACITY];
        }else {
            data = Arrays.copyOfRange(data, 0, this.size);
            this.capacity = data.length;
            if(top == this.min){
                this.min = Arrays.stream(data).min().getAsInt();
            }
        }
    }

    public int top() {
        if (this.size <=0) {
            throw new IndexOutOfBoundsException("stack is empty");
        }
        return data[this.size-1];
    }

    public int getMin() {
        if (this.size <=0) {
            return 0;
        }
        return this.min;
    }

    private void grow() {
        int oldCapacity = this.capacity;
        // 扩容 oldCapacity + oldCapacity*2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - DEFAULT_CAPACITY < 0)
            newCapacity = DEFAULT_CAPACITY;
        // minCapacity is usually close to size, so this is a win:
        data = Arrays.copyOf(data, newCapacity);
        this.capacity = data.length;
    }

    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */


}
